package airthmetic.exercise.fibonacci;

/**
 * @Author douhy
 * @description 斐波那契数列  leetCode 509 https://leetcode-cn.com/problems/fibonacci-number
 * @date 22/01/13
 */
public class FibonacciNumberDemo {

    // 0 1 1 2 3 5 8 13 ...
    // 思路 下一个数是上一个数与上上一个数的和
    public static Integer fib(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;

        while (n-- > 1) {
            second += first;
            first = second - first;
        }
        return second;
    }

    // 递归做法
    public static Integer fib2(int n) {
        if (n <= 1) return n;
        return fib2(n - 1) + fib(n - 2);
    }

    // 数学，线性代数解决 不是所有的算法问题都恰巧有数学公式解决!!!
    public static Integer fib3(int n) {
        double sqrt = Math.sqrt(5);
        return (int) ((Math.pow((1 + sqrt) / 2 ,n)-Math.pow((1 - sqrt) / 2, n)) /sqrt);
    }


    public static void main(String[] args) {
        System.out.println(fib(100000));
        System.out.println(fib2(100000));
//        System.out.println(fib3(55));
    }
}
